package leetcode.editor.cn;

//Given two sorted arrays nums1 and nums2 of size m and n respectively, return 
//the median of the two sorted arrays. 
//
// The overall run time complexity should be O(log (m+n)). 
//
// 
// Example 1: 
//
// 
//Input: nums1 = [1,3], nums2 = [2]
//Output: 2.00000
//Explanation: merged array = [1,2,3] and median is 2.
// 
//
// Example 2: 
//
// 
//Input: nums1 = [1,2], nums2 = [3,4]
//Output: 2.50000
//Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
// 
//
// 
// Constraints: 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -10⁶ <= nums1[i], nums2[i] <= 10⁶ 
// 
// Related Topics 数组 二分查找 分治 👍 5506 👎 0

import java.util.Arrays;

class MedianOfTwoSortedArrays{
    public static void main(String[] args) {
        Solution solution = new MedianOfTwoSortedArrays().new Solution();

        solution.findMedianSortedArrays(new int[] { 1, 2},
                new int[]{3,4});
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // respectively
        double v = way1(nums1, nums2);
        System.out.println(v);
        return v;
    }
    private  double way1(int[] nums1, int[] nums2){
        //
        int[] all = mergeArray1(nums1, nums2);
        //
//        System.out.println("合并后的数组为：");
//        Arrays.stream(all).forEach(System.out::println);
        // 取中位数
        int length = all.length;
        if (length%2==0){
            // 除2能取整数，则要取中间两位
            int i = length / 2;
            double res = (double) (all[i-1]+all[i] ) / 2;
            return res;
        }else{
            int i =  length/2;
            return all[i];

        }
    }

    private int[] mergeArray1(int[] nums1, int[] nums2){
        int[] all = new int[nums1.length+nums2.length];
        // nums1 下标
        int i = 0;
        // Nums2 下标
        int j = 0;
        // all 下标
        int k = 0;
        while(i<nums1.length && j<nums2.length){
            if (nums1[i]<nums2[j]){
                all[k++] = nums1[i++];
            }
            else{
                all[k++] = nums2[j++];
            }
        }
        // 将nums1 或者nums2剩余元素添加
        while(i<nums1.length){
            all[k++] = nums1[i++];
        }
        while(j<nums2.length){
            all[k++] = nums2[j++];
        }
        return all;

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}